---
title: "1980. Find Unique Binary String"
created: 2025-12-19
---
# 1980. Find Unique Binary String

## 题目 [**1980. Find Unique Binary String**](https://leetcode.com/problems/find-unique-binary-string/)

![[image-a6137b9f.png]]

## 思路分析

![[image-4d617675.png]]

### 康托对角线法 (Cantor's Diagonalization)

这是一道经典的数学题变种。我们不需要枚举所有可能性，我们只需要**构造**出一个和现有所有字符串都不同的串即可。

核心逻辑：

只要我们构造的字符串 ans，满足：

- 第 **0** 位字符，和 `nums[0]` 的第 **0** 位**不同** \(\to\) 保证了 `ans` 不等于 `nums[0]`
- 第 **1** 位字符，和 `nums[1]` 的第 **1** 位**不同** \(\to\) 保证了 `ans` 不等于 `nums[1]`
- ...
- 第 **i** 位字符，和 `nums[i]` 的第 **i** 位**不同** \(\to\) 保证了 `ans` 不等于 `nums[i]`

这样构造出来的 `ans`，就一定不等于 `nums` 中的任何一个字符串！

举例：

nums = ["01", "10"]

1. 看 `nums[0]` ("01") 的第 0 位是 `'0'` \(\to\) 我们的结果第 0 位取反，选 `'1'`。
2. 看 `nums[1]` ("10") 的第 1 位是 `'0'` \(\to\) 我们的结果第 1 位取反，选 `'1'`。
3. 结果是 `"11"`。

## 代码实现

```java
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n=nums.length;
        Set<String> set = new HashSet<>();
        for(String s:nums){
            set.add(s);
        }
        for(int i=0;i<(1<<n);i++){
            StringBuilder sb = new StringBuilder(Integer.toBinaryString(i));
            //前导零
            while(sb.length()<n){
                sb.insert(0,"0");
            }
            String current = sb.toString();
            if(!set.contains(current)){
                return current;
            }
        }
        return "";
    }
}
```

```java
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n=nums.length;
        Set<String> set = new HashSet<>();
        for(String s:nums){
            set.add(s);
        }
        for(int i=0;i<(1<<n);i++){
            /*
            利用 1 << n (即 2^n) 强行在最前面加一个 1，把后面撑开，
            然后转成字符串后截取掉最前面的 1。
            假设 n=5，要把 5 (101) 变成 00101：
            1 << 5 是 100000 (二进制)。
            (1 << 5) | 5 变成 100101。
            转成字符串 "100101"。
            从索引 1 开始截取 substring(1) 
            to "00101"。
            */
            String current = Integer.toBinaryString((1<<n)|i).substring(1);

            if(!set.contains(current)){
                return current;
            }
        }
        return "";
    }
}
```

```java
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        StringBuilder sb = new StringBuilder();

        // 只需要遍历一次数组
        for (int i = 0; i < nums.length; i++) {
            // 取出第 i 个字符串的第 i 个字符
            char c = nums[i].charAt(i);

            // 如果是 '0' 就变成 '1'，如果是 '1' 就变成 '0'
            // 并拼接到结果中
            sb.append(c == '0' ? '1' : '0');
        }

        return sb.toString();
    }
}
```

## 同类题型

## 视频讲解